import java.util.*;

public class project {
    public int characterReplacement(String s, int k) {
        int max=0;
        int left=0;
        int right=0;
        int[] arr=new int[26];
        int len=s.length();
        while (right<len){
            char ch=s.charAt(right);
            arr[ch-'A']++;
            max=Math.max(max,arr[ch-'A']);
            if(right-left+1-max>k){
                arr[s.charAt(left)-'A']--;
                left++;
            }
            right++;
        }
        return right-left;
    }
























    public int minMutation(String start, String end, String[] bank) {
        Deque<String> deque=new ArrayDeque<>();
        List<String> list=Arrays.asList(bank);
        Map<String ,Integer> map=new HashMap<>();
        map.put(start,0);
        deque.add(start);
        String[] str={"A","T","C","G"};
        while (!deque.isEmpty()){
            String s=deque.poll();
            for(int i=0;i<8;i++){
                for(int j=0;j<4;j++){
                    if(String.valueOf(s.charAt(i)).equals(str[j])){
                        continue;
                    }
                    String tmp=s.substring(0,i)+str[j]+s.substring(i+1,s.length());
                    if(!list.contains(tmp)){
                        continue;
                    }
                    if(!map.containsKey(tmp)){
                        map.put(tmp,map.get(s)+1);
                        deque.add(tmp);
                        if(tmp.equals(end)){
                            return map.get(tmp);
                        }
                    }
                }
            }
        }
        return -1;

    }



















    HashSet<List<Integer>> hashSet=new HashSet<>();
    List<Integer> list=new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(nums,0);
        List<List<Integer>> ret=new ArrayList<>(hashSet);
        return ret;
    }
    public void dfs(int[] nums,int index){
        if(list.size()>1){
            hashSet.add(new ArrayList<>(list));
        }
        for(int i=index;i<nums.length;i++){
            if(list.size()==0||nums[i]>=list.get(list.size()-1)){
                list.add(nums[i]);
                dfs(nums,i+1);
                list.remove(list.size()-1);
            }
        }
    }

















    public int beautySum(String s) {
        int len=s.length();
        int ret=0;
        for(int i=0;i<len;i++){
            int[] arr=new int[26];
            for(int j=i;j<len;j++){
                char ch=s.charAt(i);
                arr[ch-'a']++;
                int max=Integer.MIN_VALUE;
                int min=Integer.MAX_VALUE;
                for (int value:arr){
                    if(value!=0&&value>max){
                        max=value;
                    }
                    if(value!=0&&value<min){
                        min=value;
                    }
                }
                ret+=(max-min);
            }
        }
        return ret;
    }

























    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        List<Integer> list=new ArrayList<>();
        PriorityQueue<Integer> queue1=new PriorityQueue<>();
        for(int i=0;i<k;i++){
            queue1.offer(i);
        }
        PriorityQueue<int[]> queue2=new PriorityQueue<>((a,b)->a[0]-b[0]);
        int[] arr=new int[k];
        for(int i=0;i<arrival.length;i++){
            while (!queue2.isEmpty()&&queue2.peek()[0]<=arrival[i]){
                int id=queue2.peek()[1];
                queue2.poll();
                queue1.offer(i+((id-i)%k+k)%k);
            }
            if(queue1.isEmpty()){
                continue;
            }
            int server= queue1.poll()%k;
            arr[server]++;
            queue2.offer(new int[]{arrival[i]+load[i],server});
        }
        int max=0;
        for(int i=0;i<k;i++){
            if(arr[i]==max){
                list.add(i);
            }else if(arr[i]>max){
                list.clear();
                max=arr[i];
                list.add(i);
            }
        }
        return list;
    }
}
